1. Field of the Invention
This invention relates to the time sharing of user defined devices in a multi-tasking computer system and, in particular, to the synchronization of user defined devices connected to the system through the memory management unit.
2. Art Background
Computers range in size, features, and capabilities from personal computers to large mainframes. Many computers are capable of multi-tasking; that is, the processes running on the system share the resources of the system, e.g. CPU, co-processor, memory and devices, so that more than one process can be running or appear to be running concurrently. The multi-tasking capability is achieved through the "sharing" (also referred to as "time-sharing") of the resources by the processes. The operating system gives each process a turn to utilize the resources, typically for a predetermined amount of time. When it is another process's turn to utilize the resource, the current process is suspended; and the state of the process is stored until it is the process's turn again to utilize the resource. For example, in some UNIX-based systems, a scheduler allocates the CPU and co-processor, such as a floating point processor (FPU), to processes. It schedules the processes to run in turn until they voluntarily relinquish the CPU and FPU while awaiting another resource or until the operating system preempts the process when the run time exceeds a time quantum.
When the operating system switches the CPU or CPU's (if the system is configured with multiple CPU's) from process to process it has to save the state of the process which is not currently running (such a process is referred to as "inactive") so that when the operating system switches the CPU back to run an inactive process (the inactive process thereby becoming "active"), the process will resume its execution at the point it was stopped earlier. The information that needs to be saved and restored in order to resume execution in the same state in which the process was earlier stopped is referred to as the context of the process. When executing a process, the system is said to be executing in the context of the process. Thus, when the operating system determines that it should execute another process, it performs what is referred to as a "context switch" so that the system can execute in the context of the other process. The context switch comprises the steps of saving the context of the active process which had been running at the time of the context switch and restoring the context of the inactive process to be activated so that process will resume at the point it was stopped by an earlier context switch. The context contains such information as the values of the process's global user variables and data structures, the values of machine registers which the process uses, and other data that may be needed to continue the running of the process at a later time.
Context switching is illustrated in the diagram of FIG. 1. At time t0, Process 1 is active and Processes 2 and 3 are inactive. At time t1, a context switch is performed in which the context of the CPU and FPU with respect to Process 1 is stored in the operating system data structure (In a UNIX-based operating system, this data structure typically comprises a system process table and save area.) and the context of the CPU and FPU with respect to Process 2 is retrieved from the operating system data structure and restored on the CPU and FPU so that the CPU and FPU resume their execution in the context of Process 2. Similarly, at time t2 a context switch is performed in which the context of the CPU and FPU with respect to Process 2 is stored in the operating system data structure and the context of the CPU and FPU with respect to Process 3 are restored on the CPU and FPU.
The computer systems currently available typically support the CPU and FPU as devices which are time-shared among processes. Thus, the operating system recognizes the two devices and knows what elements comprise the state of the processor to be preserved when context switching is performed. Additional processors or devices are often connected to the system through the memory management unit (MMU) using a well known technique referred to as memory mapped input/output (I/O). Each device connected through the MMU has an address state which represents the public state a process can access. The CPU accesses the device using the address in the same manner as if the device were memory.
As the sophistication of computer systems increase, so do the number of specialized devices or processors (hereinafter collectively referred to as "user defined devices") which perform specific, typically time consuming, functions thereby distributing the processing load and increasing the overall processing speed of the system. These user defined devices are typically attached to the system through the MMU. For example, many computer systems utilize graphics processors to perform the time consuming computations required to generate a graphic display or vector processors to perform vector calculations. However, the operating system cannot utilize the same techniques and processes which are used to provide a full multi-tasking capability of the CPU and FPU to provide a multi-tasking capability of the user defined devices because the context and characteristics of each device is different. Thus, the increase in speed provided by the user defined devices is minimized by absence of a time share capability among multiple processes.
Several problems arise when multiple processes access user defined devices which are connected through the MMU. One problem arises with respect to the context switching of the devices. Although multiple processes have access to the same user-defined device, only one process can access the device at a time regardless of what context the kernel is operating in because the kernel does not provide for the context switching of a device connected to the system through the MMU. Thus, a process which accesses a device through the MMU controls the device until it is finished accessing the device.
The problem that arises is best described by example. Two processes, Process 1 and 2, are currently running on the system and both process utilize a device such as a vector processor which is connected through the MMU. Process 1 has control of the CPU and is the active process. Process 1 attempts to access the device first by checking the device lock to see if access to the device is permitted. If the device lock is not set, Process 1 is not be able to access the device and has to wait, i.e., go to "sleep", until the device is not locked and Process 1 is the active process. If the device lock is not set, Process 1 sets the device lock to prevent any other process from accessing the device and loads the device with the context information required for the device operate with Process 1. If a process switch occurs which renders Process 1 inactive and Process 2 active, when Process 2 attempts to access the device, it will discover that the device is locked because Process 1 has not finished accessing the device. Thus, Process 2 will have to go to sleep until Process 1 is finished accessing the device. When Process 1 is finished accessing the device, the context information from Process 1 is read from the device and stored in a system data structure, such as the save area in the UNIX operating system, and the device is unlocked, thereby permitting other processes to access the device.
Another problem arises when the operating system receives a command from a process to be assembled and subsequently sent to the device to complete execution of the command. The command when assembled may consist of multiple words containing various attributes of the command. Errors occur when control of the CPU switches from a first process to a second process and the entire command had not been transferred to the device. The command is lost because the process does not realize that the complete command was not transferred to the device, and therefore the process will not retransfer the command when the process subsequently has control of the CPU. Furthermore the operating system has no mechanism to save the command which is partially loaded into the device.
Still another problem arises with respect to the control of process flow. To control the flow and execution of a number of commands with respect to a particular device, a queue is typically used to store the commands in sequence and send one command at a time to the device. However, the queue is of a limited size and can overflow, thereby losing those commands which cannot be stored in the overflowed queue. This problem can be decreased somewhat by providing a separate device queue for each process that accesses the device. However, overflow problems can still occur if the process accesses the device frequently.
Serialization and synchronization problems also arise with respect to devices connected through the MMU. Serialization problems occur when a process executes two commands with respect to the same device, and the first command is transmitted through the queue so that it reaches the device after the second command which is not transmitted through the queue. Synchronization problems arise when multiple processes interact with one another and require that one process execute certain commands with respect to a device before another process executes commands. For example, if the device connected through the MMU is a graphics device and Process 1 contains commands to load the color table while Process 2 contains commands to draw a graphics image, the Process 1 command has to be executed prior to the Process 2 commands in order that the proper colors are utilized to portray the graphics image.